package data_structures_and_algorithms.bit_arithmetic;

/**
 * @ClassName _56_1_singleNumbers
 * @Description: 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [3,4,3,3]
 * 输出：4
 * 示例 2：
 *
 * 输入：nums = [9,1,7,9,7,9,7]
 * 输出：1
 *  
 *
 * 限制：
 *
 * 1 <= nums.length <= 10000
 * 1 <= nums[i] < 2^31
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/11 12:40
 */
public class _56_2_singleNumbers {

    public static void main(String[] args) {

        int[] nums = new int[]{3,2,2,2};
        int i = new _56_2_singleNumbers().singleNumber(nums);
        System.out.println(i);
    }

    public int singleNumber(int[] nums) {
        // 创建一个32位数组，存储各个位数上1出现的次数总和
        int[] counts = new int[32];
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            num = nums[i];
            for (int j = 0; j < 32; j++) {
                counts[j] += (num & 1);
                num = num >>> 1;
            }
        }

        // 取余 计算结果
        int res = 0;
        for (int i = counts.length - 1; i >= 0; i--) {
            counts[i] %= 3;
            res = (res << 1) + counts[i];
        }

        return res;
    }
}
